//实现一个二叉搜索树，包括增、删、查功能
public class SearchBinaryTree {
    //首先需要创建二叉树的节点类
    static class TreeNode {
        public int val;
        public TreeNode leftTree;
        public TreeNode rightTree;

        public TreeNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }

    public TreeNode root = null;

    //从二叉搜索树中查找数据
    public TreeNode searchTree(int val) {
        //首先将根节点赋值给cur
        TreeNode cur = root;
        if (root == null) {
            return root;
        }
        while (cur != null) {
            //判断根节点是否存在该元素
            if (val == cur.val) {
                return cur;
            } else if (val < cur.val) {
                cur = cur.leftTree;
            } else {
                cur = cur.rightTree;
            }
        }
        return null;
    }


    //向二叉搜索树中插入数据
    public void insertTreeNode(int val) {
        //首先将节点创建出来
        TreeNode newNode = new TreeNode(val);
        //如果是一个空树，那么可以直接将其作为根节点
        if (root == null) {
            root = newNode;
            return;
        }
        TreeNode cur = root;
        //要确保值不重复
        while (cur.val != val) {
            if (cur.val > val) {
                if (cur.leftTree == null) {
                    cur.leftTree = newNode;
                    System.out.println("插入成功:" + val);
                    return;
                }
                cur = cur.leftTree;
            } else {
                if (cur.rightTree == null) {
                    cur.rightTree = newNode;
                    System.out.println("插入成功:" + val);
                    return;
                }
                cur = cur.rightTree;
            }
        }
        System.out.println("插入失败，要插入的值与原有的元素重复:" + val);
    }


    /**
     * 删除二叉搜索树中的节点
     *
     * @param val
     */
    public void removeTreeNode(int val) {
        TreeNode cur = root;
        TreeNode prev = root;
        //首先需要先找到要删除的节点
        if (root == null) {
            System.out.println("该二叉搜索树没有节点，无法删除!");
            return;
        }
        while (cur != null) {
            //判断根节点是否存在该元素
            if (val == cur.val) {
                break;
            } else if (val < cur.val) {
                prev = cur;
                cur = cur.leftTree;
            } else {
                prev = cur;
                cur = cur.rightTree;
            }
        }
        if (cur == null) {
            System.out.println("没有你要删除的数据");
            return;
        }
        //找到之后需要判断该节点的左右是否为空
        if (cur.leftTree == null && cur.rightTree == null) {//左右都为空
            if(cur == root){
                root = null;
                System.out.println("删除成功");
                return;
            }
            if (cur == prev.leftTree) {
                prev.leftTree = null;
            }
            if (cur == prev.rightTree) {
                prev.rightTree = null;
            }
        } else if (cur.leftTree == null) {//左空右不空
            if(cur == root){
                root = root.rightTree;
                System.out.println("删除成功");
                return;
            }
            if (cur == prev.leftTree) {
                prev.leftTree = cur.rightTree;
            }
            if (cur == prev.rightTree) {
                prev.rightTree = cur.rightTree;
            }
        } else if (cur.rightTree == null) {//左不空右空
            if (cur == prev.rightTree) {
                prev.rightTree = cur.leftTree;
            }
            if (cur == prev.leftTree) {
                prev.leftTree = cur.leftTree;
            }
        }else{//左右都不为空，从cur的左侧找到最大值或从cur的右侧找到最小值
            TreeNode ret = cur.leftTree;
            TreeNode prevRet = ret;
            while(ret.rightTree != null) {
                prevRet = ret;
                ret = ret.rightTree;
            }
            //交换要删除的节点和找到的节点
            int tmp = ret.val;
            ret.val = cur.val;
            cur.val = tmp;
            prevRet.rightTree = null;
        }
        System.out.println("删除成功");
    }
}
